#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_V 8 // 顶点数（A-H）

// 邻接表结点结构
typedef struct AdjListNode
{
    int vertex;               // 邻接顶点索引
    struct AdjListNode *next; // 指向下一个邻接结点
} AdjListNode;

// 顶点结构
typedef struct
{
    char name;         // 顶点名称
    AdjListNode *head; // 邻接表头指针
    int visited;       // 访问标记
} Vertex;

// 图结构
typedef struct
{
    Vertex vertices[MAX_V]; // 顶点数组
    int vCount;             // 当前顶点数
} Graph;

// 创建图
Graph *createGraph()
{
    Graph *g = (Graph *)malloc(sizeof(Graph));
    g->vCount = 0;
    return g;
}

// 添加顶点
void addVertex(Graph *g, char name)
{
    if (g->vCount >= MAX_V)
    {
        printf("Error: Graph is full\n");
        return;
    }
    g->vertices[g->vCount].name = name;
    g->vertices[g->vCount].head = NULL;
    g->vertices[g->vCount].visited = 0;
    g->vCount++;
}

// 添加有向边
void addEdge(Graph *g, int from, int to)
{
    if (from < 0 || from >= g->vCount || to < 0 || to >= g->vCount)
    {
        printf("Error: Invalid vertex index\n");
        return;
    }

    // 创建新结点（仅单向添加）
    AdjListNode *newNode = (AdjListNode *)malloc(sizeof(AdjListNode));
    newNode->vertex = to;
    newNode->next = g->vertices[from].head;
    g->vertices[from].head = newNode;
}

// 深度优先遍历（递归）
void DFS(Graph *g, int currentIndex)
{
    // 访问当前顶点
    g->vertices[currentIndex].visited = 1;
    printf("%c ", g->vertices[currentIndex].name);

    // 按邻接表顺序递归访问未访问的邻接顶点
    AdjListNode *node = g->vertices[currentIndex].head;
    while (node)
    {
        int adjVertex = node->vertex;
        if (!g->vertices[adjVertex].visited)
        {
            DFS(g, adjVertex);
        }
        node = node->next;
    }
}

// 销毁图
void destroyGraph(Graph *g)
{
    if (!g)
        return;

    for (int i = 0; i < g->vCount; i++)
    {
        AdjListNode *node = g->vertices[i].head;
        while (node)
        {
            AdjListNode *temp = node;
            node = node->next;
            free(temp);
        }
    }
    free(g);
}

int main()
{
    // 创建图
    Graph *g = createGraph();

    // 添加顶点（A-H对应索引0-7）
    addVertex(g, 'A');
    addVertex(g, 'B');
    addVertex(g, 'C');
    addVertex(g, 'D');
    addVertex(g, 'E');
    addVertex(g, 'F');
    addVertex(g, 'G');
    addVertex(g, 'H');

    // 添加有向边（按题目要求构建）
    addEdge(g, 0, 1); // A -> B
    addEdge(g, 0, 2); // A -> C
    addEdge(g, 1, 3); // B -> D
    addEdge(g, 2, 4); // C -> E
    addEdge(g, 4, 7); // E -> H
    addEdge(g, 7, 6); // H -> G
    addEdge(g, 7, 5); // H -> F
    addEdge(g, 6, 5); // G -> F

    // 从A(0)开始深度优先遍历
    printf("DFS Traversal: ");
    DFS(g, 0);
    printf("\n");

    // 销毁图
    destroyGraph(g);

    return 0;
}